/**************************************************************************
 * Author: Chao Wang
 * Email:  chw412@lehigh.edu
 *
 * This is the vacuum agent's source code.
 * My agent has two working modes: sensing and exploring.
 * When in sensing mode, it will look around to know as much information around it as possible.
 * When in exploring mode, it will look for a goal square that needs to be explored and find a path to it.
 * When there is no goals available, the agent shuts off
 * 
 */
package chw412;

import agent.*;
import vacworld.*;

import java.util.*;
import java.lang.Comparable;

/**
 * this class represents the x and y of location points note that this class
 * implements Comparable so that two location points can compare with each
 * other. This location object also contains the reference of its parent object
 * so that we can use it to back-track the path.
 * 
 */

class location implements Comparable {
	public int x = 0;
	public int y = 0;
	public location parent = null;

	public location(int x, int y) {
		this.x = x;
		this.y = y;
		this.parent = null;
	}

	//set the parent of me
	public void set_parent_as(location p) {
		parent = p;
	}

	@Override
	public boolean equals(Object o) {
		if (o == null)
			return false;
		if (!(o instanceof location))
			return false;
		return ((location) o).x == this.x && ((location) o).y == this.y;
	}

	@Override
	public int compareTo(Object o) {
		if (o == null)
			return 1;
		else if (!(o instanceof location))
			return -1;
		else if (this.x < ((location) o).x)
			return -1;
		else if (this.x > ((location) o).x)
			return 1;
		else if (this.x == ((location) o).x && this.y < ((location) o).x)
			return -1;
		else if (this.x == ((location) o).x && this.y == ((location) o).x)
			return 0;
		else if (this.x == ((location) o).x && this.y > ((location) o).x)
			return 1;
		// TODO Auto-generated method stub
		else
			return 0;
	}
};

/**
 * this class records the basic information of agents when it gets to a new
 * square These states information may be used by the decision making process
 * for find a goal or path.s
 * 
 */
class agent_state {
	// history locations and orientations
	public int x = 0;
	public int y = 0;
	public int head = Direction.NORTH;

	// history precepts
	public boolean see_dirt = false;
	public boolean see_obstacle = false;
	public boolean feel_bump = false;

	// the action executed at this state
	public Action action = null;

	public agent_state(int x, int y, int head, boolean dirt, boolean obstacle,
			boolean bump, Action a) {
		this.x = x;
		this.y = y;
		this.head = head;
		this.see_dirt = dirt;
		this.see_obstacle = obstacle;
		this.feel_bump = bump;
		action = a;
	}
};

/**
 * An abstract software agent class. The agent must be managed by the
 * Environment class, which calls its see() and selectAction() methods.
 * 
 */
public class VacAgent extends Agent {
	// the precision used by me
	static final double eps = 0.001;
	// the size of the map I will be wandering.
	static final int MAX_X = 7;
	static final int MAX_Y = 7;
	static final int x_size = MAX_X << 1;
	static final int y_size = MAX_Y << 1;

	// the representation of obstacle and clear space in my map.
	// VISITED represents whether this space has already been visited by me.
	// note that although each space can only be one of these. they can also be
	// VISITED or not.
	static final int UNKNOWN = 1;
	static final int CLEAR = 2;
	static final int OBSTACLE = 4;
	static final int VISITED = 8;
	static final int BFS_MARK = 16;

	// this is the internal VacPercet that stores directly from the method see.
	protected VacPercept my_percept;

	// this is the history of states /w actions that I have ever been (doing).
	protected Stack<agent_state> state_history;

	// this is the map in my mind, which is of size MAX_X<<1 * MAX_Y<<1 in
	// maximum.
	int[][] my_map = new int[x_size][y_size];

	// the next action selected (i.e., the action decided to executed)
	Action next_action = null;

	// my initial position and orientation.
	// note that I assume I stand at position (MAX_X, MAX_Y), facing NORTH
	protected int cur_x = MAX_X;
	protected int cur_y = MAX_Y;
	protected int cur_head = Direction.NORTH;

	// stages of my agent:
	// Sensing, Acting
	// each time when the agent moves to a new place, it starts with sensing
	// mode;
	// after it knows the other fours places well around it, it gets into the
	// exploring mode.
	protected enum stage {
		sensing, // the agent is sensing the environment around it.
		exploring, // the agent is exploring new free space
	};

	// the enumeration of four relative direction: front, right, back and left
	protected enum direction {
		front, right, back, left
	};

	protected enum sensing_mode {
		none, // do not need any sensing
		only_left, // only the left space is unknown, so turn left, then
					// complete sensing
		only_right, // only the right space is unknown, so turn right, then
					// complete sensing
		left_back, // left and back unknown
		right_back, // right and back unknown
		left_back_right // left, right and back unknown
	}

	// the agent starts with sensing mode. i.e., it senses environment(its place
	// and the other four places) around it.
	stage st = stage.sensing;
	// the agent starts with sensing the front.
	direction sens_st = direction.front;
	// the agent assumes the worst case: left space and right space are unknown;
	// so it needs to sensing at least 3 turns.
	sensing_mode sens_m = sensing_mode.left_back_right;

	// the next location ready to explore if any
	location next_to_explore = null;
	// the plan, i.e., the list of actions(GoForward, TurnLeft, TurnRight) to
	// reach the next location.
	Queue<Action> plan = null;
	// the steps(locations) needed when walking from current location to the
	// target location.
	Stack<location> steps = null;

	/**
	 * the constructor of an agent
	 * 
	 */
	public VacAgent() {
		super();
		state_history = new Stack<agent_state>();
		plan = new LinkedList<Action>();
		steps = new Stack<location>();

		// set my map as clear as possible when I was born
		// also set all spaces as unvisited
		for (int i = 0; i < MAX_X << 1; ++i)
			for (int j = 0; j < MAX_Y << 1; ++j)
				my_map[i][j] = UNKNOWN & ~VISITED;
	}

	/**
	 * update my relative position and orientation information. note that
	 * initially, my agent assumes that it is located at position (0,0), facing
	 * NORTH. this method should be called only after the next_action has been
	 * effectively decided.
	 **/

	protected void update_location_and_orientation() {
		if (next_action instanceof GoForward) {
			switch (cur_head) {
			case Direction.NORTH:
				cur_y += 1;
				break;
			case Direction.EAST:
				cur_x += 1;
				break;
			case Direction.SOUTH:
				cur_y -= 1;
				break;
			case Direction.WEST:
				cur_x -= 1;
				break;
			default:
				assert (false);
				break;
			}
		} else if (next_action instanceof TurnLeft) {
			switch (cur_head) {
			case Direction.NORTH:
				cur_head = Direction.WEST;
				break;
			case Direction.EAST:
				cur_head = Direction.NORTH;
				break;
			case Direction.SOUTH:
				cur_head = Direction.EAST;
				break;
			case Direction.WEST:
				cur_head = Direction.SOUTH;
				break;
			default:
				assert (false);
				break;
			}
		} else if (next_action instanceof TurnRight) {
			switch (cur_head) {
			case Direction.NORTH:
				cur_head = Direction.EAST;
				break;
			case Direction.EAST:
				cur_head = Direction.SOUTH;
				break;
			case Direction.SOUTH:
				cur_head = Direction.WEST;
				break;
			case Direction.WEST:
				cur_head = Direction.NORTH;
				break;
			default:
				assert (false);
				break;
			}
		} else if (next_action instanceof ShutOff
				|| next_action instanceof SuckDirt) {
			// we do not need to update the position and orientation information
			// of the agent in these cases.
		}
	}

	// test if position (x,y) is visited
	protected boolean is_unknown(int x, int y) {
		return (my_map[x][y] & UNKNOWN) != 0;
	}

	// test if position l is visited
	protected boolean is_unknown(location l) {
		return (my_map[l.x][l.y] & UNKNOWN) != 0;
	}

	// test if position (x,y) is visited
	protected boolean is_visited(int x, int y) {
		return (my_map[x][y] & VISITED) != 0;
	}

	// test if position l is visited
	protected boolean is_visited(location l) {
		return (my_map[l.x][l.y] & VISITED) != 0;
	}

	// test if position (x,y) is clear
	protected boolean is_clear(int x, int y) {
		return (my_map[x][y] & CLEAR) != 0;
	}

	// test if position l is clear
	protected boolean is_clear(location l) {
		return (my_map[l.x][l.y] & CLEAR) != 0;
	}

	// test if position (x,y) has obstacle
	protected boolean has_obstacle(int x, int y) {
		return (my_map[x][y] & OBSTACLE) != 0;
	}

	// test if position l has obstacle
	protected boolean has_obstacle(location l) {
		return (my_map[l.x][l.y] & OBSTACLE) != 0;
	}

	/**
	 * given that I am at position l, facing D, If I moved toward direction d,
	 * the next x position would be:
	 * 
	 * @param l
	 *            the current location.
	 * @param D
	 *            the direction that current agent is facing.
	 * @param d
	 *            the relative direction that the agent is turning to.
	 * @return the next location that the agent would face if it did so.
	 */
	protected int next_x(location l, int D, direction d) {
		switch (d) {
		case front:
			switch (D) {
			case Direction.NORTH:
			case Direction.SOUTH:
				return l.x;
			case Direction.EAST:
				return l.x + 1;
			case Direction.WEST:
				return l.x - 1;
			default:
				assert (false);
				return -1;
			}
		case right:
			switch (D) {
			case Direction.NORTH:
				return l.x + 1;
			case Direction.SOUTH:
				return l.x - 1;
			case Direction.EAST:
			case Direction.WEST:
				return l.x;
			default:
				assert (false);
				return -1;
			}
		case back:
			switch (D) {
			case Direction.NORTH:
			case Direction.SOUTH:
				return l.x;
			case Direction.EAST:
				return l.x - 1;
			case Direction.WEST:
				return l.x + 1;
			default:
				assert (false);
				return -1;
			}
		case left:
			switch (D) {
			case Direction.NORTH:
				return l.x - 1;
			case Direction.SOUTH:
				return l.x + 1;
			case Direction.EAST:
			case Direction.WEST:
				return l.x;
			default:
				assert (false);
				return -1;
			}
		default:
			assert (false);
			return -1;
		}
	}

	/**
	 * given that I am at position l, facing D, If I moved toward direction d,
	 * the next y position would be:
	 * 
	 * @param l
	 *            the current location.
	 * @param D
	 *            the direction that current agent is facing.
	 * @param d
	 *            the relative direction that the agent is turning to.
	 * @return the next location that the agent would face if it did so.
	 */
	protected int next_y(location l, int D, direction d) {
		switch (d) {
		case front:
			switch (D) {
			case Direction.NORTH:
				return l.y + 1;
			case Direction.SOUTH:
				return l.y - 1;
			case Direction.EAST:
			case Direction.WEST:
				return l.y;
			default:
				assert (false);
				return -1;
			}
		case right:
			switch (D) {
			case Direction.NORTH:
			case Direction.SOUTH:
				return l.y;
			case Direction.EAST:
				return l.y - 1;
			case Direction.WEST:
				return l.y + 1;
			default:
				assert (false);
				return -1;
			}
		case back:
			switch (D) {
			case Direction.NORTH:
				return l.y - 1;
			case Direction.SOUTH:
				return l.y + 1;
			case Direction.EAST:
			case Direction.WEST:
				return l.y;
			default:
				assert (false);
				return -1;
			}
		case left:
			switch (D) {
			case Direction.NORTH:
			case Direction.SOUTH:
				return l.y;
			case Direction.EAST:
				return l.y + 1;
			case Direction.WEST:
				return l.y - 1;
			default:
				assert (false);
				return -1;
			}
		default:
			assert (false);
			return -1;
		}
	}

	/**
	 * return the next location according to current loc and direction
	 * 
	 * @param l
	 *            the current location.
	 * @param D
	 *            the direction that current agent is facing.
	 * @param d
	 *            the relative direction that the agent is turning to.
	 * @return the next location that the agent would face if it did so.
	 * 
	 */
	protected location next_loc(location l, int D, direction d) {
		return new location(next_x(l, D, d), next_y(l, D, d));
	}

	/**
	 * decide the sensing mode.
	 * 
	 * @return the sensing mode detected: possibles are: left_back_right,
	 *         left_back, right_back, only_left, only_right and none.
	 */
	sensing_mode decide_sensing_mode() {
		location cur = new location(cur_x, cur_y);
		boolean left = (my_map[next_x(cur, cur_head, direction.left)][next_y(
				cur, cur_head, direction.left)] == UNKNOWN);
		boolean right = (my_map[next_x(cur, cur_head, direction.right)][next_y(
				cur, cur_head, direction.right)] == UNKNOWN);
		boolean back = (my_map[next_x(cur, cur_head, direction.back)][next_y(
				cur, cur_head, direction.back)] == UNKNOWN);

		if (left && right)
			return sensing_mode.left_back_right;
		else if (left && back && !right)
			return sensing_mode.left_back;
		else if (right && back & !left)
			return sensing_mode.right_back;
		else if (!left && !right && back)
			return sensing_mode.left_back;
		else if (left && !right && !back)
			return sensing_mode.only_left;
		else if (!left && right && !back)
			return sensing_mode.only_right;
		else
			return sensing_mode.none;
	}

	/**
	 * this function is used by the BFS at the start of each goal-seeking
	 * process so that each position is not marked.
	 */
	public void clear_all_marks() {
		for (int j = 0; j < y_size; ++j) {
			for (int i = 0; i < x_size; ++i) {
				my_map[i][j] &= ~BFS_MARK;
			}
		}
	}

	/**
	 * This function plays the key role in finding out the next location
	 * available for exploring.
	 * 
	 * @return the next location to explore from near to far respect to current
	 *         location
	 */
	location find_next_loc_to_explore() {
		clear_all_marks();

		location ret = null;
		Queue<location> v1 = new LinkedList<location>();
		location cur_loc = new location(cur_x, cur_y);
		v1.add(cur_loc);
		my_map[cur_x][cur_y] |= BFS_MARK;

		while (!v1.isEmpty()) {
			location t = v1.remove();

			// test if any location is unvisited
			if (!is_visited(t)) {
				ret = t;
				for (location i = ret; i != cur_loc; i = i.parent)
					steps.push(i);
				return ret;
			}

			direction[] dirs = { direction.front, direction.right,
					direction.left, direction.back };
			for (direction is : dirs) {
				location temp = next_loc(t, cur_head, is);
				if (!is_unknown(temp) && !has_obstacle(temp)
						&& (my_map[temp.x][temp.y] & BFS_MARK) == 0) {
					my_map[temp.x][temp.y] |= BFS_MARK;
					v1.add(temp);
					temp.set_parent_as(t);
				}
			}
		}

		// we tried our best, if found, return the next loc to explore,
		// if not, return null
		return null;
	}

	/**
	 * get the vector corresponding to the Direction d
	 * 
	 * @param d
	 *            the current direction.
	 * @return the vector of this direction.
	 */
	location direction_vector(int d) {
		switch (d) {
		case Direction.NORTH:
			return new location(0, 1);
		case Direction.EAST:
			return new location(1, 0);
		case Direction.SOUTH:
			return new location(0, -1);
		case Direction.WEST:
			return new location(-1, 0);
		default:
			assert (false);
			return null;
		}
	}

	/**
	 * print the map that the agent has explored.
	 */
	void print_my_map() {
		for (int j = y_size - 1; j >= 0; --j) {
			for (int i = 0; i < x_size; ++i) {
				if (is_unknown(i, j)) {
					System.out.print("|+|");
				} else if (has_obstacle(i, j)) {
					System.out.print("|X|");
				} else if (is_visited(i, j)) {
					System.out.print("|v|");
				} else
					System.out.print("|c|");
			}
			System.out.println();
		}
	}

	/**
	 * if I turned right, I will be facing direction:
	 * 
	 * @param d
	 *            the relative direction the agent is turning to.
	 * @return the next direction the agent will be facing.
	 */
	int turn_right(int d) {
		switch (d) {
		case Direction.NORTH:
			return Direction.EAST;
		case Direction.EAST:
			return Direction.SOUTH;
		case Direction.SOUTH:
			return Direction.WEST;
		case Direction.WEST:
			return Direction.NORTH;
		default:
			assert (false);
			return -1;
		}
	}

	/**
	 * if I turned left, I will be facing direction:
	 * 
	 * @param d
	 *            the relative direction the agent is turning to.
	 * @return the next direction the agent will be facing.
	 */
	int turn_left(int d) {
		switch (d) {
		case Direction.NORTH:
			return Direction.WEST;
		case Direction.EAST:
			return Direction.NORTH;
		case Direction.SOUTH:
			return Direction.EAST;
		case Direction.WEST:
			return Direction.SOUTH;
		default:
			assert (false);
			return -1;
		}
	}

	/**
	 * 
	 * @param l
	 *            my current location
	 * @param D
	 *            my current direction
	 * @return the next location if I go forward from current location
	 */
	location go_forward(location l, int D) {
		switch (D) {
		case Direction.NORTH:
			return new location(l.x, l.y + 1);
		case Direction.EAST:
			return new location(l.x + 1, l.y);
		case Direction.SOUTH:
			return new location(l.x, l.y - 1);
		case Direction.WEST:
			return new location(l.x - 1, l.y);
		default:
			assert (false);
			return null;
		}
	}

	/**
	 * the cosine_similarity of two vectors
	 * 
	 * @param vector1
	 *            the first vector
	 * @param vector2
	 *            the second vector
	 * @return the cosine similarity of these two vectors.
	 */
	double cosine_similarity(location vector1, location vector2) {
		return (vector1.x * vector2.x + vector1.y * vector2.y)
				/ Math.sqrt(vector1.x * vector1.x + vector1.y * vector1.y);
	}

	/**
	 * generate a plan of going to the square dst from our current location
	 * 
	 * @param dst
	 *            the destination
	 * @return a queue of Actions by which I can go fron current location to the
	 *         destination location.
	 */
	Queue<Action> generate_plan(location dst) {
		// TODO modify this
		Queue<Action> temp = new LinkedList<Action>();
		// if the steps stack is not empty, then we generate the plan from this
		// stack
		if (!steps.empty()) {
			int next_x = cur_x;
			int next_y = cur_y;
			int next_dir = cur_head;
			while (!steps.empty()) {
				location t = steps.pop();
				// TODO
				location vec_dir = direction_vector(next_dir);
				location vec_step = new location(t.x - next_x, t.y - next_y);
				double cos = cosine_similarity(vec_dir, vec_step);

				// here we decide if we need any turn(s) before going forward
				// to the next location in the steps
				if (Math.abs(cos + 1.0) < eps) {
					temp.add(new TurnRight());
					temp.add(new TurnRight());
					next_dir = turn_right(next_dir);
					next_dir = turn_right(next_dir);
				} else if (Math.abs(cos) < eps) {
					int temp_dir = turn_right(next_dir);
					location vec_temp_dir = direction_vector(temp_dir);
					double cos2 = cosine_similarity(vec_temp_dir, vec_step);
					if (Math.abs(cos2 + 1.0) < eps) {
						temp.add(new TurnLeft());
						next_dir = turn_left(next_dir);
					} else if (Math.abs(cos2 - 1.0) < eps) {
						temp.add(new TurnRight());
						next_dir = turn_right(next_dir);
					} else
						assert (false);
				} else if (Math.abs(cos - 1.0) < eps) {
					// do not need any turns
				}

				// move forward to the next step
				temp.add(new GoForward());
				next_x = t.x;
				next_y = t.y;
			}
		} else { // do not have steps information
			assert (false);
		}

		return temp;
	}

	/**
	 * after finishing looking around and familiarize myself with the
	 * environment, I started explore the world around me.
	 * 
	 * @return the next action selected.
	 */
	Action explore() {
		// if the plan is not empty, we get one Action from the plan
		// and use it as the next action
		if (!plan.isEmpty()) {
			return plan.remove();
		}

		// now the plan is empty, so we need to generate another goal to achieve
		// and generate the corresponding plan of achieving it.

		// now we decide whether we have known unvisited square that is ready to
		// explore
		next_to_explore = find_next_loc_to_explore();
		if (next_to_explore != null) {
			// generate a plan to reach the desired goal.
			plan = generate_plan(next_to_explore);
			if (plan.isEmpty()) // there is no way of achieving that goal, give
								// up
				return new ShutOff();
			else {
				return plan.remove();
			}
		} else { // all spaces are either unreachable(i.e., being obstacle) or
					// visited, we need to re-consider whether it is time
					// to stop the job
			// TODO re-consider before stop working
			return new ShutOff();
		}
	}

	/**
	 * Provide a Percept to the agent. This function is called by the
	 * environment at the beginning of each agent's turn. If the agent has
	 * internal state, this method should also update it.
	 */

	public void see(Percept p) {
		my_percept = (VacPercept) p;

		// if I see any dirt, we must suck it immediately to avoid heavy
		// penalty.
		if (my_percept.seeDirt()) {
			next_action = new SuckDirt();
			return;
		}

		// the automation deciding what to do according to the stage the agent
		// is now at.
		switch (st) {
		case sensing:
			// I am in the sensing stage. now sense the environment in front of
			// me.
			location cur = new location(cur_x, cur_y);
			if ((my_map[next_x(cur, cur_head, direction.front)][next_y(cur,
					cur_head, direction.front)] & UNKNOWN) != 0) {
				// if I see obstacles in front of me. I memorize this info in my
				// database
				// If not, I memorize it as clear space.
				if (my_percept.seeObstacle() || my_percept.feelBump()) {
					my_map[next_x(cur, cur_head, direction.front)][next_y(cur,
							cur_head, direction.front)] &= ~UNKNOWN;
					my_map[next_x(cur, cur_head, direction.front)][next_y(cur,
							cur_head, direction.front)] |= OBSTACLE;
				} else {
					my_map[next_x(cur, cur_head, direction.front)][next_y(cur,
							cur_head, direction.front)] &= ~UNKNOWN;
					my_map[next_x(cur, cur_head, direction.front)][next_y(cur,
							cur_head, direction.front)] |= CLEAR;
				}
			}

			switch (sens_st) {
			case front:
				my_map[cur_x][cur_y] &= ~UNKNOWN;
				my_map[cur_x][cur_y] |= CLEAR;
				my_map[cur_x][cur_y] |= VISITED;
				// need to decide if I need to turn or not.
				// find if we really need to sense the other direction
				// and how to sense it.
				sens_m = decide_sensing_mode();

				switch (sens_m) {
				case left_back_right:
				case left_back:
				case only_left:
					st = stage.sensing;
					sens_st = direction.left;
					next_action = new TurnLeft();
					break;
				case right_back:
				case only_right:
					st = stage.sensing;
					sens_st = direction.right;
					next_action = new TurnRight();
					break;
				case none:
					st = stage.exploring; // now we come to the exploring mode
					next_action = explore();
					if (next_action instanceof GoForward) {
						st = stage.sensing;
						sens_st = direction.front;
					}
					break;
				default:
					assert (false);
					break;
				}
				break;
			case right:
				switch (sens_m) {
				case left_back_right:
				case only_right:
					st = stage.exploring; // now we come to the exploring mode
					next_action = explore();
					if (next_action instanceof GoForward) {
						st = stage.sensing;
						sens_st = direction.front;
					}
					break;
				case right_back:
					st = stage.sensing;
					sens_st = direction.back;
					next_action = new TurnRight();
					break;
				default:
					assert (false);
					break;
				}
				break;
			case back:
				switch (sens_m) {
				case left_back_right:
					st = stage.sensing;
					sens_st = direction.right;
					next_action = new TurnLeft();
					break;
				case left_back:
				case right_back:
					st = stage.exploring; // now we come to the exploring mode
					next_action = explore();
					if (next_action instanceof GoForward) {
						st = stage.sensing;
						sens_st = direction.front;
					}
					break;
				default:
					assert (false);
					break;
				}
				break;
			case left:
				switch (sens_m) {
				case left_back_right:
				case left_back:
					st = stage.sensing;
					sens_st = direction.back;
					next_action = new TurnLeft();
					break;
				case only_left:
					st = stage.exploring;
					next_action = explore();
					if (next_action instanceof GoForward) {
						st = stage.sensing;
						sens_st = direction.front;
					}
				}
				break;
			default:
				break;
			}
			break;
		case exploring:
			my_map[cur_x][cur_y] |= ~UNKNOWN & CLEAR & VISITED; // set current
																// place as
																// visited
			st = stage.exploring; // now we come to the exploring mode
			next_action = explore();
			if (next_action instanceof GoForward) {
				st = stage.sensing;
				sens_st = direction.front;
			}
			break;
		}

		// push the current state of agent into stack for future reference
		state_history.push(new agent_state(cur_x, cur_y, cur_head, my_percept
				.seeDirt(), my_percept.seeObstacle(), my_percept.feelBump(),
				next_action));

		// up until now, the next_action has been decided. So we update the
		// internal information stored.
		update_location_and_orientation();

		// System.out.println(state_history);
		// System.out.println("now I am at : (" + cur_x + "," + cur_y +
		// "), facing: " + Direction.toString(cur_head));
		// print_my_map();
	}

	/**
	 * Have the agent select its next action to perform. Implements the action0:
	 * Per -> Ac function or the action: I -> Ac function, depending on whether
	 * or not the agent has internal state. Note, Per (or I) is not passed as a
	 * parameter, because we assume this information is recorded in an instance
	 * variable by the see() method.
	 */
	public Action selectAction() {
		// since we have already found the next action based on the agent's
		// knowledge,
		// we just return the found action.
		return next_action;
	}

	/**
	 * Return a unique string that identifies the agent. This is particularly
	 * useful in multi-agent environments.
	 */
	public String getId() {
		return "chw412's VacAgent";
	}
}
